893F - Subtree Minimum Query - CodeForces Solution

#include <bits/stdc++.h>
using namespace std ;
const int N = 100005 ;
const int INF = 0x3f3f3f3f ;
int n, m, a[N], rt, dep[N], tot = 0, siz[N], dfn[N], root[N], D = 0, sumd = 0, ans, ste = 0 ;
int dl[N] ;
vector<int> df[N] ;
vector<int> G[N] ;
struct segment_tree
{
	int l, r, w ;
}t[N * 20] ;
void dfs(int x, int fa)
{
	dfn[x] = ++ste ;
	siz[x] = 1 ;
	dep[x] = dep[fa] + 1 ;
	D = max(D, dep[x]) ;
	for(int i = 0 ;i < G[x].size(); i ++)
	{
		int y = G[x][i] ;
		if(y == fa) continue ;
		dfs(y, x) ;
		siz[x] += siz[y] ;
	}
	return ;
}
int build_tree(int l, int r)
{
	int now = ++tot ;
	if(l == r)
	{
		t[now].w = INF ;
		return now ;
	}
	int mid = (l + r) >> 1 ;
	t[now].l = build_tree(l, mid) ;
	t[now].r = build_tree(mid + 1, r) ;
	t[now].w = INF ;
	return now ;
}
int update(int pre, int l, int r, int id, int num)
{
	int now = ++tot ;
	t[now] = t[pre] ;
//	if(t[now].w == 0) printf("!!!\n") ;
	if(l == r)
	{
		t[now].w = min(t[now].w, num) ;
		return now ;
	}
	int mid = (l + r) >> 1 ;
	if(id <= mid) t[now].l = update(t[pre].l, l, mid, id, num) ;
	else t[now].r = update(t[pre].r, mid + 1, r, id, num) ;
	t[now].w = min(t[t[now].l].w, t[t[now].r].w) ;
	return now ;
} 
int query(int x, int l, int r, int L, int R)
{
	if(L <= l && r <= R) 
	{
		return t[x].w ;
	}
	int mid = (l + r) >> 1 ;
	if(l > R || r < L) return INF ;
	int ans = query(t[x].l, l, mid, L, R) ;
	ans = min(ans, query(t[x].r, mid + 1, r, L, R)) ;
	return ans ;
} 
int main()
{
	scanf("%d%d", &n, &rt) ;
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]) ;
	for(int i = 1; i <= n - 1; i ++)
	{
		int u, v ;
		scanf("%d%d", &u, &v) ;
		G[u].push_back(v) ;
		G[v].push_back(u) ;
	}
//	printf("!\n") ;
	dfs(rt, 0) ;
//	printf("!\n")
	for(int i = 1; i <= n; i ++)
	{
		df[dep[i]].push_back(i) ;
//		printf("%d %d %d\n", siz[i], dep[i], dfn[i]) ;
//		printf("%d\n", dfn[i]) ;
	}
//	printf("%d!\n", D) ;
	root[sumd] = build_tree(1, n) ;
//	printf("!\n") ;
//	printf("%d!\n", t[root[sumd]].w) ;
	for(int i = 1; i <= D; i ++)
	{
		for(int j = 0; j < df[i].size(); j ++)
		{
			int x = df[i][j] ;
//			printf("%d\n", x) ;
			sumd ++ ;
			root[sumd] = update(root[sumd - 1], 1, n, dfn[x], a[x]) ;
//			printf("%d %d %d\n", x, t[root[sumd]].w, t[root[sumd - 1]].w) ;
		}
		dl[i] = sumd ;
		
	}
	scanf("%d", &m) ;
	for(int i = 1; i <= m; i ++)
	{
		int x, k ;
		scanf("%d%d", &x, &k) ;
		x = (x + ans) % n + 1 ;
		k = (k + ans) % n ;
//		printf("%d %d %d %d!!\n", root[dl[min(dep[x] + k, D)]], dfn[x], dfn[x] + siz[x] - 1, dep[x]) ;
		ans = query(root[dl[min(dep[x] + k, D)]], 1, n, dfn[x], dfn[x] + siz[x] - 1) ;
		printf("%d\n", ans) ;
	}
}
/*
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3

8 1
1 2 3 4 5 6 7 8
1 2
1 3
2 4
2 5
3 6
6 7
6 8
100
6 5
*/